/* spectral_div.h */

#ifndef _SPECTRAL_DIV_H_

#define _SPECTRAL_DIV_H_

#define IS_POSITIVE(X) ((X) > 0.00001)

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "modularity_mat.h"

/*
 *	Convenient macro definitions.
 */
#if !defined(max)
#define max(a, b)       ((a) > (b) ? (a) : (b))
#define min(a, b)       ((a) < (b) ? (a) : (b))
#endif

/*
 *	Structure representing an eigen pair
 */
typedef struct eigenpair
{
	/* The eigenvector */
	elem* eigenvector;
	/* The corresponding eigenvalue */
	elem  eigenvalue;
} eigenpair;

/*
 *	Creating a sub matrix of A according to group g
 *	-----------------------------------------------
 *	A: The original sparse matrix
 *	g: The current group of nodes
 *	elements_no: The number of elements in the vector g
 *	return: Newly allocated sub matrix of A
 *	-------------------------------------------------------------------
 *	(!) The user is responsible of releasing the returned sparse matrix
 */
sparse_matrix_lst* create_A_g(sparse_matrix_lst* A, int* g, int elements_no);

/*
 *	Creating the first vector with increasing numbers, as there is very little
 *	chance of it to be the actual eigen vector
 *	---------------------------------------------------------------------------
 *	n: The size of the vector
 *	return: Newly allocated vector
 *	------------------------------------------------------------
 *	(!) The user is responsible of releasing the returned vector
 */
elem* create_X(int n);

/*
 *	Creating the D sparse matrix
 *	----------------------------
 *	f: The vector to be placed on the diagonal of the result matrix
 *	elements_no: The number of elements in f
 *	return: D sparse matrix
 *	-------------------------------------------------------------------
 *	(!) The user is responsible of releasing the returned sparse matrix
 */
sparse_matrix_lst* create_D(elem* f, int elements_no);

/* 
 *	Creating a sub vector of ranks according to g
 *	---------------------------------------------
 *	k: The ranks of all nodes
 *	g: The sub group we are interested in
 *	elements_no: The number of elements in g
 *	return: Sub vector of k according to the nodes in g
 *	------------------------------------------------------------
 *	(!) The user is responsible of releasing the returned vector
 */
elem* create_k_g(elem* k, int* g, int elements_no);

/* 
 *	Calculating the ||B^|| value
 *	----------------------------
 *	gen_B_g: Sub matrix of the generalized modularity matrix according to g
 *	elements_no: The size of gen_B_g
 *	return: The normal of gen_B_g
 */
elem calc_norm_1(elem** gen_B_g, int elements_no);

/* 
 *	Calculate the eigenvalue 
 *	------------------------
 *	Xm: Previous closest candidate for eigen vector
 *	Xm_1: Current candidate for eigen vector
 *	elements_no: The size of the vectors
 *	return: Compatible eigenvalue
 */
elem calculate_eigenvalue(elem* Xm, elem* Xm_1, int elements_no);

/*
 *	The fast calculation method - calculating the next possible eigenvector
 *	-----------------------------------------------------------------------
 *	result: The next candidate for an eigenvector
 *	g: The current sub group
 *	X: The previous eigenvector
 *	A_g: The current sub adjacency matrix
 *	D: The D matrix (holding f on its diagonal)
 *	k_g: The ranks of nodes in g
 *	M: The total ammount of ranks
 *	norm_1_gen_B: ||B^g||
 *	elements_no: The number of elements in the g sub group
 */
void fast_calculation(elem* result, int* g, elem* X, sparse_matrix_lst* A_g,
					  sparse_matrix_lst* D, elem* k_g, elem M, 
					  elem norm_1_gen_B, int elements_no);

/* 
 *	Calculating the geometric length of a vector
 *	--------------------------------------------
 *	v: The vector we calculate the length for
 *	n: The length of the vector
 *	return: The geometric length of the vector
 */
elem geometric_length(elem* v, int n);

/* 
 *	Normalizes the vector in place by dividing all elements by the largest 
 *	value in the vector
 *	----------------------------------------------------------------------
 *	v: The vector to normalize
 *	n: The length of the vector
 */
void normalize_vector(elem* v, int n);

/* 
 *	Function testing the requirement ||Xm_1 - lambda*Xm|| <= precision*||Xm||
 *	-------------------------------------------------------------------------
 *	Xm: The previous candidate for eigenvector
 *	Xm_1: The current candidate for eigenvector
 *	precision: The epsilon to meet the requirement
 *	lambda: The last eigenvalue
 *	n: The size of the eigenvectors
 *	return: A positive value if the inequality persists
 */
int requirement_met(elem* Xm, elem* Xm_1, elem precision, elem lambda, int n);

/* 
 *	Finds eigenpair of a given generalized modularity matrix
 *	--------------------------------------------------------
 *	A_g: The current sub adjacency matrix
 *	gen_B_g: The sub generalized modularity matrix according to g
 *	k_g: The ranks of the nodes in g
 *	f: The modularity function
 *	M: The total ammount of ranks
 *	g: The sub group we work on
 *	elements_no: The number of elements in g
 *	precision: The precision that the eigenpair has to meet
 *	return: The calculated eigenpair
 *	--------------------------------------------------------
 *	(!) The user is responsible of releasing the eigenvector
 */
eigenpair find_eigenpair(sparse_matrix_lst* A_g, elem** gen_B_g, 
						 elem* k_g, elem* f, elem M, int* g, int elements_no, 
						 elem precision);

/* 
 *	Creates s by eigenvector
 *	------------------------
 *	s: The vector we fill
 *	g: The original group
 *	eigenvector: The eigenvector containing the division of g
 *	size: The length of g
 */
void compute_s(elem* s, int* g, elem* eigenvector, int size);

/*
 *	Creates the g1, g2 sub groups according to the s division
 *	---------------------------------------------------------
 *	s: The vector showing the division
 *	g: The group we divide
 *	g1: The result first group (indices of positive values in s) - out
 *	g2: The result second group (indices of negative values in s) - out
 *	g1_size: The size of the first group - out
 *	g2_size: The size of the second group - out
 *	size: The size of g
 */
void div_indices(elem* s, int* g, int** g1, int** g2, int* g1_size, 
				 int* g2_size, int size);

/*	
 *	---------------------------------------------------------------------------
 *	Help Functions
 *	---------------------------------------------------------------------------
 */

/* 
 *	Multiplying a vector by a matrix
 *	--------------------------------------------------
 *	result: The result vector
 *	vector: The vector to be multiplied
 *	matrix: The matrix to be multiplied by
 *	size: The size of the vector
 */
void mult_vector_matrix(elem* result, elem* vector, elem** matrix, int size);

/* 
 *	Multiplying two vectors
 *	-----------------------------------------
 *	vector_a: The vector to be multiplied
 *	vector_b: The vector to be multiplied by
 *	size: The size of the vectors
 *	return: The multiplication result
 */
elem mult_vector_vector(elem* vector_a, elem* vector_b, int size);

/* 
 *	Summing two vectors 
 *	-------------------
 *	result: The result of the summing
 *	vec_a: The first vector to be summed
 *	vec_b: The second vector to be summed
 *	size: The size of the vectors
 */
void vectors_sum (elem* result, elem* vec_a, elem* vec_b, int size);

/* 
 *	Subtracting two vectors
 *	-----------------------
 *	result: The result of the subtraction
 *	vec_a: The vector we subtract from
 *	vec_b: The vector to be subtracted
 *	size: The size of the vectors
 */
void vectors_difference (elem* result, elem* vec_a, elem* vec_b, int size);

/* 
 *	Multiplying a vector by a scalar
 *	--------------------------------
 *	result: The result vector
 *	vector: The vector to be multiplied
 *	scalar: The scalar to be multiplied by
 *	size: The size of the vector
 */
void mult_vector_scalar(elem* result, elem* vector, elem scalar, int size);

/*
 *	Multiply a matrix by a vector 
 *	-----------------------------
 *	result: The result vector
 *	mat:	The matrix that is to be multiplied by a vector
 *	vec:	The vector by which the matrix is being multiplied
 *	size:	The matrix / vector's size
 */
void mult_matrix_vector(elem* result, elem** mat, elem* vec, int size);

/* 
 *	Prints groups by ascending order according to the 1st element of each group
 *	---------------------------------------------------------------------------
 *	g1:		 The first subgroup in g
 *	g2:		 The second subgroup in g
 *	g1_size: g1 vector size
 *	g2_size: g2 vector size
 */
void print_groups(int* g1, int* g2, int g1_size, int g2_size);

/* 
 *	Prints a single group
 *	---------------------
 *	g:		The vector we want to print
 *	size:	The vector size
 */
void print_group(int* g, int size);

#endif 
